from graph import Graph

class DFSGraph(Graph):
    def __init__(self):
        super().__init__()
        self.time = 0   # 设置一个时间

    def dfs(self):
        for aVertex in self:
            aVertex.setColor('white')
            aVertex.setPred(-1)

        # 这里进行深度优先搜索时为什么要遍历：原因是可能有些顶点和其他顶点是不相连的，通过遍历可以确保每个顶点都能得到遍历。
        # 通过判断颜色是否为白色可以将之前判断过的顶点舍弃，实现节点只遍历一次
        for aVertex in self:
            if aVertex.getColor() == 'white':
                self.dfsVisit(aVertex)

    def dfsVisit(self,startVertex):
        startVertex.setColor('gray')    # 标记正在遍历
        self.time += 1
        startVertex.setDiscovery(self.time) # 发现时间

        for nextVertex in startVertex.getConnections():
            if nextVertex.getColor == 'white':
                nextVertex.setPred(startVertex)
                self.dfsVisit(nextVertex)

        # 可以理解为该节点遍历完了
        startVertex.setColor('black')
        self.time += 1
        startVertex.setFinish(self.time)

